package com.arron.algorithm.leetcodetop100.回溯;

import java.util.ArrayList;
import java.util.List;

public class 括号生成 {


    List<String> res;
    public List<String> generateParenthesis(int n) {

        //n 对括号表示有2n个字符
        res = new ArrayList<>();
        StringBuffer sb = new StringBuffer();
        generateParenthesis(sb,0,0,n);

        return res;
    }

    public void generateParenthesis(StringBuffer  sb, int left,int right,int n){

        if (left>n || right>n){
            return;
        }
        //当左括号的数量小于右括号的数量的时候组合是无效的括号组合
        if (left < right){
            return;
        }
        if (left+right == 2*n){
            res.add(sb.toString());
            return;
        }
        //选择左括号
        sb.append("(");
        generateParenthesis(sb,left+1,right,n);
        sb.deleteCharAt(sb.length()-1); //撤销选择

        //选择右括号
        sb.append(")");
        generateParenthesis(sb,left,right+1,n);
        sb.deleteCharAt(sb.length()-1);//撤销选择


    }


    public static void main(String[] args) {
//        StringBuffer sb = new StringBuffer();
//
//        sb.append("(");
//        sb.append(")");
//        sb.deleteCharAt(sb.length()-1);
//        System.out.println(sb.toString());
        括号生成 parenthesis = new 括号生成();

        System.out.println(parenthesis.generateParenthesis(2));
    }





}
